Search for: All records

A k-dispersed labelling of a graph G on n vertices is a labelling of the vertices of G by the integers 1,...,n such that d(i,i+1) ≥ k for 1 ≤ i ≤ n − 1. Here DL(G) denotes the maximum value of k such that G has a k-dispersed labelling. In this paper, we study upper and lower bounds on DL(G). Computing DL(G) is NP-hard. However, we determine the exact value of DL(G) for cycles, paths, grids, hypercubes and complete binary trees. We also give a product construction and we prove a degree-based bound. 

We consider ordered pairs (X,B) where X is a finite set of size v and B is some collection of k-element subsets of X such that every t-element subset of X is contained in exactly λ "blocks'' b ∈B for some fixed λ. We represent each block b by a zero-one vector c_b of length v and explore the ideal I(B) of polynomials in v variables with complex coefficients which vanish on the set { c_b ∣ b ∈ B}. After setting up the basic theory, we investigate two parameters related to this ideal: γ1(B) is the smallest degree of a non-trivial polynomial in the ideal I(B) and γ2(B) is the smallest integer s such that I(B) is generated by a set of polynomials of degree at most s. We first prove the general bounds t/2 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k.